﻿using System.Collections.Generic;
using System.Linq;

/// <summary>
/// 树结构
/// </summary>
public class Tree<T>
{
    public Node root { get; private set; }

    public Tree(string key, T value)
    {
        root = new Node(key, value);
    }

    public Node Find(string key, SearchMode mode = SearchMode.Depth)
    {
        if (root.key == key) return root;
        if (root.isLeaf) return null;
        switch (mode)
        {
            default:
            case SearchMode.Depth:
                return FindWithDepth(key, root);
            case SearchMode.Breadth:
                return FindWithBreadth(key, root);
        }
    }

    private Node FindWithDepth(string key, Node parent)
    {
        foreach (var child in parent.children)
        {
            if (child.key == key) return child;
            if (child.isLeaf) continue;
            var node = FindWithDepth(key, child);
            if (node != null) return node;
        }
        return null;
    }

    private Node FindWithBreadth(string key, Node parent)
    {
        var queue = new Queue<Node>();
        foreach (var child in parent.children)
        {
            queue.Enqueue(child);
        }
        while (queue.Count > 0)
        {
            var item = queue.Dequeue();
            if (item.key == key) return item;
            if (item.isLeaf) continue;
            foreach (var child in item.children)
            {
                queue.Enqueue(child);
            }
        }
        return null;
    }

    public enum SearchMode
    {
        /// <summary>
        /// 深度优先查找
        /// </summary>
        Depth,
        /// <summary>
        /// 广度优先查找
        /// </summary>
        Breadth
    }

    /// <summary>
    /// 节点子类
    /// </summary>
    public class Node
    {
        public string key { get; private set; }
        public T value { get; private set; }
        public Node parent { get; set; }
        public HashSet<Node> children { get; private set; } = null;

        public Node(string key, T value)
        {
            this.key = key;
            this.value = value;
        }

        public bool isLeaf => children == null || children.Count <= 0;

        public string path => parent != null ? $"{parent.path}/{key}" : key;

        public Node FindChild(string key)
        {
            if (children == null) return null;
            return children.FirstOrDefault(node => node.key == key);
        }

        public Node AddChild(string key, T value)
        {
            return AddChild(new Node(key, value));
        }

        public Node AddChild(Node child)
        {
            if (children == null)
            {
                children = new HashSet<Node>();
            }
            var matchedNode = children.FirstOrDefault(node => node.key == key);
            if (matchedNode != null)
            {
                return matchedNode;
            }
            child.parent = this;
            children.Add(child);
            return child;
        }

        public Node RemoveChild(string key)
        {
            if (children == null) return null;
            var child = children.FirstOrDefault(node => node.key == key);
            return RemoveChild(child);
        }

        public Node RemoveChild(Node child)
        {
            if (children == null) return null;
            children.Remove(child);
            return child;
        }
    }
}
